In SSDs (solid state drive), when a data erasing unit (block) is different from a data management unit, according to the progress of rewriting of a flash memory, blocks are made porous by invalid (non-latest) data. When blocks in such a porous state increase, substantially usable blocks decrease and a storage area of the flash memory cannot be effectively used. Therefore, for example, when the number of free blocks (unused blocks which do not include valid data therein and for which a use is not allocated) of the flash memory becomes less than a predetermined threshold, the flash memory is organized, for example, by performing compaction of collecting valid data in blocks and rewriting the data in a different block, thereby reserving a free block for which a use is not allocated.
That means that a block having a small amount of valid data that is a target for the compaction can be released after moving the data, therefore, the number of free blocks can be increased by the compaction. In the compaction processing, it is needed to determine whether data in a movement source block is valid data or invalid data. Thus, it is needed to prepare a reverse lookup address translation table (translation table from NAND address into host address: Reverse Lookup Table) in a memory. A translation table from a host address into a NAND address is a forward lookup address translation table (Lookup Table).
If the compaction continues to be performed when a write request is input from a host device to an SSD, the response to the write request is delayed. If the compaction is not performed, for example, free blocks cannot be reserved, therefore, the compaction needs to be performed in some cases. However, when free blocks are present even if the compaction is not performed, it is desirable to prioritize the response to a write request.
Moreover, a recording method in a NAND flash memory includes a multi-value recording (MLC: Multi-Level Cell) method and a binary recording (SLC: Single-Level Cell) method. Whereas the SLC method (hereinafter, SLC mode) records 1 bit in one cell that is one unit for recording, the MLC method (hereinafter, MLC mode) can record N bits (N>1) in one cell. Therefore, for example, in a MLC flash memory that records 2 bits per cell, one cell can express four values, and, in a MLC flash memory that records 3 bits per cell, one cell can express eight values.
Thus, in the recording in the MLC mode, the recording capacity per volume can be increased compared with that in the recording in the SLC mode, and there is a merit that the cost per recording capacity can be suppressed. On the other hand, in the recording in the SLC mode, there is a merit that the access time in writing and reading is short and the reliability is high compared with the recording in the MLC mode.